package zuoshen_video;

import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;

public class HeapSort {

    public void buildHeap(int[] nums) {
        int p;
        for (int i = 0; i < nums.length; i++) {
            int cur = i;
            while (nums[cur] > nums[(p = (cur - 1) / 2)]) {
                swap(nums, cur, p); //若当前节点大于父节点，将父节点与其交换，直到没有父节点或者父节点大于等于当前节点
                cur = p;
            }
        }
    }

    public void heapify(int[] nums, int start, int size) {
        int l, r, i = start, len = size, max;
        while (i < len) {
            max = i;
            if ((l = 2 * i + 1) < len && nums[l] > nums[max]) max = l;
            if ((r = 2 * i + 2) < len && nums[r] > nums[max]) max = r;
            if (max == i) {
                break;
            } else {
                swap(nums, i, max);
                i = max;
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    class MiddleNumber {

        //简单方法：利用API做
        public double getMiddle1(int[] nums) {
            Queue<Integer> min = new PriorityQueue<>((i1, i2) -> i2 - i1);
            Queue<Integer> max = new PriorityQueue<>();

            for (int i = 0; i < nums.length; i++) {
                if (min.size() == max.size()) {
                    //若两者的数量相等，优先存入大根堆
                    max.offer(nums[i]);
                    min.offer(max.poll()); //此时，会导致小根堆数量多一个
                } else {
                    min.offer(nums[i]);
                    max.offer(min.poll()); //此时，两者数量相等
                }
            }
            System.out.println(min);
            System.out.println(max);
            return min.size() == max.size() ? ((min.peek() + max.peek()) / 2.0) : min.peek();
        }

        //另外一种可以理解的思路：
        /* 
            只有小于等于大顶堆的才会进入大顶堆，否则进入小顶堆；
            若两者的size差距大于1，将较多的那个的堆顶放到另外一个

            小根堆堆顶必然是较大一半的较小者，两者又维持基本一致，因此对于当前遍历到的部分，较小的一半一定在大根堆中

            即，两个堆维持一个状态：数平均，且较大一半在小；较小一半在大
        */
        public double getMiddle(int[] nums) {
            Queue<Integer> min = new PriorityQueue<>();
            Queue<Integer> max = new PriorityQueue<>((i1, i2) -> i2 - i1);

            for (int i = 0; i < nums.length; i++) {
                if (max.isEmpty() || nums[i] <= max.peek()) {
                    max.offer(nums[i]);
                    if (max.size() > min.size() + 1) {
                        //差距超过1
                        min.offer(max.poll());
                    }
                } else {
                    min.offer(nums[i]);
                    if (min.size() > max.size() + 1) max.offer(min.poll());
                }
            } 

            System.out.println(min);
            System.out.println(max);
            if (min.size() > max.size()) return min.peek();
            else if (min.size() < max.size()) return max.peek();
            else return (min.peek() + max.peek()) / 2.0;
        }


    }

    @Test
    public void test() {
        int[] nums = ArrayGenerator.getArray(100, 20);
        // nums = new int[]{73, 1, 67, 44, 75, 33, 43, 61, 98, 11};
        System.out.println(Arrays.toString(nums));

        buildHeap(nums);

        System.out.println(Arrays.toString(nums));

        nums[5] = 1;
        heapify(nums, 5, nums.length);
        System.out.println(Arrays.toString(nums));

    }

    @Test
    public void test2() {
        int[] nums = ArrayGenerator.getArray(100, 10);
        // nums = new int[]{73, 1, 67, 44, 75, 33, 43, 61, 98, 11};
        System.out.println(Arrays.toString(nums));
        MiddleNumber mn = new MiddleNumber();
        System.out.println(mn.getMiddle(nums));
        System.out.println(mn.getMiddle1(nums));
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));

        System.out.println((nums[4] + nums[5]) / 2.0);
    }
}
